<html>
<head>
<title>Word equations</title>
</head>

<body>

<center>
<h1>POI V Stage 2 Problem 2</h1>
<h1>Word equations</h1>
</center>

<p>
Every non-empty sequence of elements 0 and 1 is called a binary
word. A word equation is an equation of the form 
x<sub>1</sub>x<sub>2</sub>..x<sub>l</sub>=y<sub>1</sub>y<sub>2</sub>..y<sub>r</sub>, 
where
x<sub>i</sub> and y<sub>j</sub> are binary digits (0 or 1) or variables i.e. small 
letters of English alphabet. For every variable there is a
fixed length of the binary words that can be substituted for 
this variable. This length is called a length of variable. In order
to solve a word equation we have to assign binary words of 
appropriate length to all variables (the length of the word
assigned to the variable x has to be equal to the length of this variable)
in such a way that if we substitute words for variables
then both sides of the equation (which are binary words after substitution) become equal.

<p>For a given equation compute how many distinct solutions it has.


<h2>Example</h2>
Let a, b, c, d, e be variables and let 4,2,4,4,2 be their lengths 
(4 is the length of a, 2 is the length of b etc.). Consider the equation:<br>
<PRE>1bad1 = acbe</pre>
This equation has 16 distinct solutions.</p>

<h2>Task</h2>
Write a program, that
<UL>
<LI>reads  the number of equations and
their descriptions from the text file PRO.IN;
<LI>finds the number of solutions of every equation;
<LI> writes the results to the text file  ROW.OUT.
</UL>

<h2>Input</h2>
In the first line of the input file ROW.IN there is an integer x,
1 &lt;= x &lt;= 5, which denotes the number of equations. The following lines
contain descriptions of x equations. Each description consists of
6 lines. There are no empty lines between descriptions.
Each equation is described in the following way: in the first line
of the description there is an integer k,  0 &lt;= k &lt;= 26, which 
denotes the number of distinct variables in the equation.
We assume that variables are the first k small letters of English
alphabet.
In the second line there is a sequence of k positive integers 
separated by single spaces. These numbers denote the lengths of 
variables a,b,.. from the equation (the first number is
the length of a, the second - b, etc.).
There is an integer l in the third line of the description, which
is the length of the left size of equation, i.e. the
length of the word built of digits 0 or 1 and variables 
(single letters). The left side of the equation is written in the
next line as a sequence of digits and variables with no
spaces between them. The next two lines contain the description of
the right side of the equation. The first of these lines contains
a positive integer r, which is the length of the right side of the equation.
The second line contains the right side of the equation which is
encoded in the same way as the left side.
The number of digits plus sum of the lengths of variables (we count
all appearances of variables) on each side of the equation
is not greater than 10000.

<h2>Output</h2>
For every  i, 1 &lt;= i &lt;= x, your program should write
 the number of distinct solutions of the
i-th equation to the i-th line
of the output file ROW.OUT.

<h2>Sample Input</h2>
<pre>
1
5
4 2 4 4 2
5
1bad1
4
acbe
</pre>

<h2>Sample Output</h2>
<pre>
16
</pre>

</body>

</html>
